// https://pic.leetcode-cn.com/1630464499-DTtOSc-file_1630464496602
//对于每一个格子：
// 走到它的路径数 = 到达它上面格子的路径数 + 到达它左面格子的路径数
// dp[i] = dp[i - 1][j] + dp[j - 1][i]
// 最后求 dp[m - 1][n - 1]

var uniquePaths = function(m, n) {
  const dp = Array(m).fill().map(item => Array(n))// 初始化一个二维数组  其中每个元素都是0

  for (let i = 0; i < m; ++i) {
    dp[i][0] = 1
  }
  for (let i = 0; i < n; ++i) {
    dp[0][i] = 1
  }

  for (let i = 1; i < m; ++i) {
    for (let j = 1; j < n; ++j) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    }
  }
  return dp[m - 1][n - 1]
};
console.log(uniquePaths(3, 7));
